package cn.cxq.learning.heap;

import java.util.PriorityQueue;

/**
 * 牛客题霸-全部题目
 * 牛牛算数
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：1216
 * 本题知识点： 堆 数学
 *  算法知识视频讲解
 * 题目描述
 * 牛牛现在在学习计算机，他想通过计算机计算n个数的和。
 * 但是计算机计算数字的和是有花费的，比如计算x，y两个数的和，需要花费(c*x+c*y)(c∗x+c∗y)秒。
 * 计算机一次只能计算一次，牛牛想知道自己怎么合理安排计算的顺序，可以使得花费的时间最短。
 *
 * 输出计算n个数字和的最小花费的时间。
 *
 *
 * 示例1
 * 输入
 * 复制
 * 5,76,[81,30,76,24,84]
 * 返回值
 * 复制
 * 48944
 * 示例2
 * 输入
 * 复制
 * 5,70,[1,2,3,3,4]
 * 返回值
 * 复制
 * 2030
 * 备注:
 * 给定a数组，ai表示第i个数的大小。
 *
 * 1 \leq n\leq 2*10^{5}1≤n≤2∗10
 * 5
 *   , 1 \leq c\leq 1001≤c≤100
 * 1 \leq a_{i} \leq 10^{2}1≤a
 * i
 * ​
 *  ≤10
 * 2
 */
public class CountCost {
    // 有时候 掌握一个优秀的数据结构也是很重要的
    public long solve(int n, int c, int[] a) {
        // write code here
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // 小顶堆

        for (int i = 0; i < a.length; i++) {
            heap.offer(a[i]);
        }

        long cost = 0;

        while (heap.size() > 1) {
            int num1 = heap.poll();
            int num2 = heap.poll();
            int temp = num1 + num2;
            cost += c * num1 + c * num2;
            heap.offer(temp);
        }

        return cost;
    }
}
